#include<stdio.h>

typedef int ElemType;

//创建链表
typedef struct node
{
    ElemType data;
    struct node *next; 
}Node;

//单链表的初始化
Node* initList()
{   //创建头节点
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;   //返回head指针
}

//双指针找到链表倒数第k个节点
int FindNodeFS(Node *L,int k)
{
    Node *fast = L->next;
    Node *slow = L->next;
    for(int i = 0; i < k; i++)
    {
        fast = fast->next;
    }

    while(fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    printf("倒数第%d个节点的值为%d\n", k ,slow->data);
    return 1;
}

//查找两个节点共同后缀的起始位置
Node* FindIntersectionNode(Node *headA, Node *headB)
{
    if(headA == NULL || headB == NULL)
    {
        return NULL;
    }
    Node *p = headA;
    int lenA = 0;
    int lenB = 0;

    //遍历链表A，获取链表A的长度
    while(p != NULL)
    {
        p = p->next;
        lenA++;
    }
    //遍历链表B，获取链表B的长度  
    p =headB;
    while(p != NULL)
    {
        p = p->next;
        lenB++;
    }

    Node *fast;
    Node *slow;
    int step; //两个链表之间的差值，用于快指针先走步数
    if(lenA > lenB)
    {
        step = lenA - lenB;
        fast = headA;
        slow = headB;
    }
    else
    {
        step = lenB - lenA;
        fast = headB;
        slow = headA;
    }
    //快指针先走step步
    for(int i = 0; i < step; i++)
    {
        fast = fast->next;
    }
    //快慢指针同步走，直到指向同一个节点
    while(fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

//删除绝对值相同的节点
void removeNode(Node *L, int n) //n为链表中最大值
{
    Node *p = L;
    int index; //作为数据下标使用
    int *q = (int*)malloc(sizeof(int)*(n+1));

    //遍历数组，初始化值为0
    for(int i = 0; i < n+1; i++)
    {
        *(q + i) = 0;
    }

    while(p->next != NULL)
    {
        //abs获取绝对值
        index = abs(p->next->data);
        if(*(q + index) == 0)
        {
            *(q + index) = 1;
            p = p->next;
        }
        else
        {
            Node *temp = p->next;
            p->next = temp->next;
            free(temp);
        }
    }
    free(q);
}

//反转链表
Node* reverseList(Node* head)
{
    Node *first = NULL;
    Node *second = head->next;
    Node *third;

    while(second != NULL)
    {
        third = second->next;
        second->next = first;
        first = second;
        second = third;
    }
    
    Node *hd = initList();
    hd->next = first;
}

//删除中间节点
int delMiddleNode(Node *head)
{
    Node *fast = head->next;
    Node *slow = head;

    while(fast != NULL && fast->next != NULL)
    {
        //快指针一次走两步，慢指针一次走一步
        fast = fast->next->next;
        slow = slow->next;
    }
    //此时slow指向的便是被删节点的前一个节点
    Node *q = slow->next;
    slow->next = q->next;
    free(q);
    return 1;
}